package org.wuxinshui.boosters.nowcoder.classicQuestion;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 用递归的方法对给定的二叉树进行后序遍历。
 * 例如：
 * 给定的二叉树为{1,#,2,3},
 * <p>
 * 返回[3,2,1].
 * <p>
 * 示例1
 * 输入：
 * {1,#,2,3}
 * 返回值：
 * [3,2,1]
 *
 */
public class CC6PostorderTraversal {
    /**
     *
     * @param root TreeNode类
     * @return int整型ArrayList
     */
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        // write code here
        ArrayList<Integer> result = new ArrayList<>();
        postOrderHelper(root, result);
        return result;
    }

    private void postOrderHelper(TreeNode node, List<Integer> result) {
        if (null == node) {
            return;
        }

        postOrderHelper(node.left, result);
        postOrderHelper(node.right, result);

        result.add(node.val);
    }


    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 根据层序遍历数组构建二叉树
     * @param values 层序遍历数组，用 "#" 表示空节点
     * @return 二叉树根节点
     */
    public TreeNode buildTree(String[] values) {
        if (values == null || values.length == 0 || values[0].equals("#")) {
            return null;
        }

        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int index = 1;
        while (!queue.isEmpty() && index < values.length) {
            TreeNode currentNode = queue.poll();

            // 构建左子节点
            if (index < values.length && !values[index].equals("#")) {
                currentNode.left = new TreeNode(Integer.parseInt(values[index]));
                queue.offer(currentNode.left);
            }
            index++;

            // 构建右子节点
            if (index < values.length && !values[index].equals("#")) {
                currentNode.right = new TreeNode(Integer.parseInt(values[index]));
                queue.offer(currentNode.right);
            }
            index++;
        }

        return root;
    }

    /**
     * 解析输入字符串
     * @param input 格式如 "{1,#,2,3}"
     * @return 字符串数组
     */
    public String[] parseInput(String input) {
        // 去除花括号并按逗号分割
        String content = input.substring(1, input.length() - 1);
        return content.split(",");
    }

    // 测试代码
    public static void main(String[] args) {
        CC6PostorderTraversal solution = new CC6PostorderTraversal();

        // 测试示例：{1,#,2,3}
        String input = "{1,#,2,3}";
        System.out.println("输入: " + input);

        // 解析输入并构建二叉树
        String[] values = solution.parseInput(input);
        TreeNode root = solution.buildTree(values);

        // 后序遍历
        List<Integer> result = solution.postorderTraversal(root);
        System.out.println("输出: " + result);

        // 更多测试用例
        testVariousCases();
    }

    // 测试多种情况
    public static void testVariousCases() {
        CC6PostorderTraversal solution = new CC6PostorderTraversal();

        System.out.println("\n=== 更多测试用例 ===");

        // 测试用例1: 空树
        testCase(solution, "{#}", "空树");

        // 测试用例2: 单节点
        testCase(solution, "{1}", "单节点");

        // 测试用例3: 完整二叉树
        testCase(solution, "{1,2,3,4,5,6,7}", "完整二叉树");

        // 测试用例4: 左斜树
        testCase(solution, "{1,2,#,3,#,4}", "左斜树");

        // 测试用例5: 右斜树
        testCase(solution, "{1,#,2,#,3,#,4}", "右斜树");

        // 测试用例6: 复杂二叉树
        testCase(solution, "{1,2,3,#,4,5,6,#,#,7,8}", "复杂二叉树");
    }

    private static void testCase(CC6PostorderTraversal solution, String input, String caseName) {
        System.out.println("\n" + caseName + ":");
        System.out.println("输入: " + input);

        String[] values = solution.parseInput(input);
        TreeNode root = solution.buildTree(values);
        List<Integer> result = solution.postorderTraversal(root);

        System.out.println("输出: " + result);
    }
}
